'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-21 09:21:21
'''
'''
95. 不同的二叉搜索树 II
给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。

 

示例：

输入：3
输出：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3


tips:使用start与end进行递归，按搜索树的规则构建即可。这个是典型的递归，可是我在想的时候纠结的是如何
进行递归能使得产生的序列到一个list中。没有想过其实可以让序列作为返回值，然后遍历序列进行递归的。
值得深思。
'''

from typing import List

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        def recurse(start, end):
            if start>end:
                return [None]
            re_list = []
            for i in range(start, end+1):
                left = recurse(start, i-1)
                right = recurse(i+1, end)
                for l in left:
                    for r in right:
                        node = TreeNode(i)
                        node.left = l
                        node.right = r
                        re_list.append(node)
            return re_list
        return recurse(1, n) if n else []